package com.vinjune.algorithm.topological;

import java.util.Stack;

/**
 * @author 作者：zhangwenjun
 * @version 创建时间：2015年12月9日 下午5:22:34 类说明
 *          <p>
 *          拓扑排序
 */

public class TopologicalSort {

    int[][] graph;
    int[]   list;

    void input(int[][] graph) {
        this.graph = graph;
        list = new int[graph.length];
        calculate();
    }

    void calculate() {
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < graph.length; i++) {
            if (graph[i][0] == 0) {
                stack.push(i);
            }
        }

        int i = 0;
        while (stack.empty() != true) {
            list[i] = (Integer) stack.pop();
            for (int j = 1; j < graph[list[i]].length; j++) {
                int k = graph[list[i]][j];
                if ((--graph[k][0]) == 0) {
                    stack.push(k);
                }
            }
            i++;
        }

        if (i < graph.length) {
            System.out.println("存在环，不可排序！");
            System.exit(0);
        }
    }

    int[] getList() {
        return list;
    }

}
